package src.CodeTop;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 *
 */

public class _46Permutations {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> target = permute(nums);
        for (List<Integer> list : target) {
            System.out.println(list);
        }
    }

    public static List<List<Integer>> permute(int[] nums) {
        // 定义目标外层集合
        List<List<Integer>> target = new ArrayList<>();
        target = dfs(nums, target, 0);
        return target;
    }

    // 深搜递归
    public static List<List<Integer>> dfs(int[] nums, List<List<Integer>> target, int i) {
        // 全部排好位置
        if (i == nums.length) {
            // 定义新集合存储整型
            ArrayList<Integer> arrayList = new ArrayList<>();
            // 遍历数组并把每个元素放入集合中
            for (int k = 0 ; k < nums.length ; k++)
                arrayList.add(nums[k]);
            // 再放入目标外层集合中
            target.add(arrayList);
        }
        for (int j = i ; j < nums.length ; j++) {
            // 将后面位置的元素与当前位置交换
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;

            // 排好了当前位置，接着排下一个位置
            dfs(nums, target, i + 1);

            // 回溯恢复位置
            temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
        return target;
    }
}
